package DP;

import java.util.Arrays;

/**
 * @Classname 打家劫舍II213
 * @Description TODO
 * @Date 2023/3/28 12:36
 * @Created by xjl
 */
public class 打家劫舍II213 {

    /**
     * @description 这边只是选择的是一个数组中的结果。
      * @param: nums
     * @param: start
     * @param: end
     * @date: 2023/3/28 12:38
     * @return: int
     * @author: xjl
    */
    private int rob1(int[] nums, int start, int end) { // [start,end)
        int f0 = 0, f1 = 0;
        for (int i = start; i < end; ++i) {
            int newF = Math.max(f1, f0 + nums[i]);
            f0 = f1;
            f1 = newF;
        }
        return f1;
    }

    public int rob(int[] nums) {
        int n = nums.length;
        // 两种情况选择最大的那个
        return Math.max(nums[0] + rob1(nums, 2, n - 1), rob1(nums, 1, n));
    }


    public int rob2(int[] nums) {
        /*
            情况分类
                1. 不抢头，不抢尾
                2. 抢头，不抢尾
                3. 不抢头， 抢尾

        */
        if(nums.length <= 1){return nums.length == 0 ? 0 : nums[0];}
        int[] nums1 = Arrays.copyOfRange(nums, 1, nums.length - 1);
        int[] nums2 = Arrays.copyOfRange(nums, 0, nums.length - 1);
        int[] nums3 = Arrays.copyOfRange(nums, 1, nums.length);
        return Math.max(helper(nums1), Math.max(helper(nums2), helper(nums3)));
    }

    public int helper(int[] nums){
        if(nums.length <= 1)    {return nums.length == 0 ? 0 : nums[0];}
        int[] dp = new int[nums.length];
        int res  = Math.max(nums[0], nums[1]);
        for(int i = 0; i < nums.length; i++){
            if(i == 0)  {dp[i] = nums[0];   continue;}
            if(i == 1)  {dp[i] = Math.max(nums[0], nums[1]); continue;}
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
            res   = Math.max(res, dp[i]);
        }
        return res;
    }
}
